package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_78_子集 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_78_子集().subsets(new int[]{0,1,2}));
        System.out.println(new 力扣_78_子集().subsets(new int[]{3,2,1}));
        System.out.println(new 力扣_78_子集().subsets(new int[]{0}));
        System.out.println(new 力扣_78_子集().subsets(new int[]{1,2,3,4,5,6,30,12,22,55,44,33,66,77,88,99}));
        System.out.println(new 力扣_78_子集().subsets(new int[]{1}));
    }

    /**
    题目：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

     示例 1：
     输入：nums = [1,2,3]
     输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

     示例 2：
     输入：nums = [0]
     输出：[[],[0]]

    分析：【perfect】
       1.递归 回溯

    边界值 & 注意点：
       1.
     **/
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        Deque<Integer> deque = new ArrayDeque<>();
        recursion(nums,0,deque,res);
        return res;
    }
    /**
     *  递三要素：1.单步操作【循环不变量】 2.返回值  3.终止条件
     * @param  nums 目标数组
     * @param  start 开始节点
     * @param  res 结果存储集合
     * @param deque 前面保存的值
     **/
    private void recursion(int[] nums, int start, Deque<Integer> deque, List<List<Integer>> res) {
        if(start>nums.length-1) return;
        for (int i = start; i < nums.length; i++) {
            deque.add(nums[i]);
            res.add(new ArrayList<>(deque));
            recursion(nums,i+1,deque,res);
            deque.removeLast();
        }
    }
}
